home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericTree.h,v < prev    next >
Text File  |  1988-10-12  |  3KB  |  157 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @ * @;
  6.  
  7.  
  8. 1.1
  9. date     88.09.18.16.42.07;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @//
  25. // Define the following things:
  26. //    TREE_NAME    -- the name of the tree type
  27. //    TREE_INDEX    -- the index type; defaults to unsigned short
  28. //    TREE_KEY    -- the key type; defaults to double
  29. //    TREE_ITEM    -- the type name for an item; should be typedefed
  30. //    TREE_INDEX_NULL    -- the null value for the tree index; defaults to 65535
  31. //    TREE_BASE_CLASS    -- the base class for the new tree
  32. //
  33.  
  34. #include "Awesime.h"
  35. #include "Generic.h"
  36.  
  37. #ifndef TREE_INDEX
  38. #define TREE_INDEX unsigned short
  39. #endif
  40.  
  41. #ifndef TREE_INDEX_NULL
  42. #define TREE_INDEX_NULL 0xffff
  43. #endif
  44.  
  45. #ifndef TREE_KEY
  46. #define TREE_KEY double
  47. #endif
  48.  
  49. #ifndef TREE_BASE_CLASS
  50. #define TREE_BASE_CLASS public Awesime
  51. #endif
  52.  
  53. typedef TREE_ITEM GENERIC2(TREE_NAME,Item);
  54. typedef TREE_KEY GENERIC2(TREE_NAME,Key);
  55. typedef TREE_INDEX GENERIC2(TREE_NAME,Index);
  56.  
  57. extern const GENERIC2(TREE_NAME,Index) GENERIC2(TREE_NAME,Null);
  58.  
  59. typedef struct {
  60.     GENERIC2(TREE_NAME,Key) key;
  61.     GENERIC2(TREE_NAME,Item) item;
  62.     GENERIC2(TREE_NAME,Index) left;
  63.     GENERIC2(TREE_NAME,Index) right;
  64. } GENERIC2(TREE_NAME,Record);
  65.  
  66. class TREE_NAME : TREE_BASE_CLASS {
  67.  
  68.     GENERIC2(TREE_NAME,Record) *storage;
  69.     char *pValid;
  70.     int elements;
  71.     GENERIC2(TREE_NAME,Index) allocatedSize;
  72.     GENERIC2(TREE_NAME,Index) freelist;
  73.     GENERIC2(TREE_NAME,Index) root;
  74.  
  75.     inline GENERIC2(TREE_NAME,Index) &left(GENERIC2(TREE_NAME,Index) p) {
  76.     return(&(storage[p].left));
  77.     }
  78.  
  79.     inline GENERIC2(TREE_NAME,Index) &right(GENERIC2(TREE_NAME,Index) p) {
  80.     return(&(storage[p].right));
  81.     }
  82.  
  83.     inline GENERIC2(TREE_NAME,Key) &key(GENERIC2(TREE_NAME,Index) p) {
  84.     return(&(storage[p].key));
  85.     }
  86.  
  87.     inline GENERIC2(TREE_NAME,Item) &item(GENERIC2(TREE_NAME,Index) p) {
  88.     return(&(storage[p].item));
  89.     }
  90.  
  91.     void makeRoom(int atLeast);
  92.  
  93.     inline GENERIC2(TREE_NAME,Index) getCell() {
  94.     if (freelist == GENERIC2(TREE_NAME,Null)) {
  95.         makeRoom();
  96.     }
  97.     GENERIC2(TREE_NAME,Index) cell = freelist;
  98.     pValid[freelist] = 1;
  99.     freelist = storage[freelist].sibling;
  100.     elements++;
  101.     return(cell);
  102.     }
  103.  
  104.     inline void returnCell(GENERIC2(TREE_NAME,Index) cell) {
  105.     storage[cell].sibling = freelist;
  106.     pValid[cell] = 0;
  107.     freelist = cell;
  108.     elements--;
  109.     }
  110.  
  111. public:
  112.     TREE_NAME(int length = 0, bool xdebug = 0);
  113.  
  114.     void add(GENERIC2(TREE_NAME,Key) *key, GENERIC2(TREE_NAME,Item) *item);
  115.  
  116.     bool remove(GENERIC2(TREE_NAME,Key) *key,
  117.         GENERIC2(TREE_NAME,Item) *removed);
  118.  
  119.     inline GENERIC2(TREE_NAME,Index) minItem() {
  120.     return(root);
  121.     };
  122.  
  123.     inline bool valid(GENERIC2(TREE_NAME,Index) index) {
  124.     return ( pValid[index] );
  125.     }
  126.  
  127.     inline GENERIC2(TREE_NAME,Key) & key(GENERIC2(TREE_NAME,Index) i) {
  128.     return( storage[i].key );
  129.     }
  130.  
  131.     inline GENERIC2(TREE_NAME,Item) & item(GENERIC2(TREE_NAME,Index) i) {
  132.     return( storage[i].item );
  133.     }
  134.  
  135.     inline GENERIC2(TREE_NAME,Index) maxIndex() {
  136.     return(allocatedSize);
  137.     }
  138.  
  139.     inline bool isEmpty() {
  140.     return(elements <= 0);
  141.     }
  142.  
  143.     inline unsigned int size() {
  144.     return(elements);
  145.     }
  146.  
  147.     virtual void classPrintOn(ostream& s);
  148. };
  149.  
  150. #undef TREE_NAME
  151. #undef TREE_ITEM
  152. #undef TREE_KEY
  153. #undef TREE_INDEX
  154. #undef TREE_BASE_CLASS
  155.  
  156. @
  157.